Texture synthesis involves automatically generating large textures from a small example image (known as a texture sample or exemplar). This exemplar-based texture synthesis takes an exemplar and generates additional content based on that exemplar to create much more content than is contained in the exemplar. Exemplar-based texture synthesis alleviates the need to store explicitly an entire expanse of content. Instead, the content is generated “on the fly” from the much smaller exemplar.
Traditionally, exemplar-based texture synthesis includes a correction process that compares neighborhoods of each synthesized pixel with neighborhoods of the exemplar. The synthesized pixels then are modified to recreate synthesized neighborhoods that are compatible with the exemplar content. For each pixel, the best matching neighborhood is found, and then the current pixel is replaced with the best-matching pixel. The best-matching neighborhood is determined by comparing pixel colors in a small grid of pixels. For example, for each pixel, a 5×5 neighborhood of pixels may be examined, and the error of the neighborhood is the sum of the errors of the red, green, and blue (RGB) color vectors of individual pixels in the 5×5 neighborhood. The major problem with this traditional approach is that to properly recover the structure of the texture and ensure good matching, a fairly broad neighborhood must be examined to determine where in the “big picture” of the synthesized texture the pixel neighborhood being processed is located.
One way to mitigate this problem is to extract more information from the exemplar pixels than just their RGB color values. For example, some texture synthesis techniques transform the exemplar into a higher-dimensional space to characterize more information at each pixel than just the color. While traditional color space is three-dimensional (3-D) containing the RGB color values of a pixel, a higher-dimensional appearance space may contain additional attribute channels (and more dimensions) having additional information in addition to the RGB information. This additional information helps further distinguish the pixel from its neighbors. This additional information manifests itself in a transformed exemplar that has a higher-dimensional space than the traditional 3-D color space.
One type of texture synthesis technique that uses this transformed exemplar having a higher-dimensional appearance space is texton-based texture synthesis. In general, texton-based texture synthesis builds a higher-dimensional (more than 3-D) vector containing filter responses, clusters the pixels into textons in an appearance space, and uses a matrix to record and look up distances between textons. More specifically, the texton-based texture synthesis applies a sequence of steerable filters (or Gaussian derivative filters) to a pixel neighborhood to obtain a vector of filter responses. These are responses to filters at a series of different scales around the pixel, such as, for example, 3×3, 5×5, 7×7, etc. neighborhoods. Based on these filter-response vectors, pixels having similar appearance are clustered into groups (called “textons”), wherein each cluster is a set of pixels having similar filter responses. A matrix, called an inter-texton distance matrix, then is generated that contains the pre-computed distances between each of the textons. Each entry of the inter-texton distance matrix computes a difference between one texton and another. Thus, if two textons are similar, the matrix entry for those textons is a small value, and if they are different the entry is a large value.
There are at least two drawbacks, however, to texton-based texture synthesis. First, the clustering process introduces errors into the texture synthesis process. In particular, clustering process treats all pixels in the same cluster as being identical, even if their neighborhoods are not completely similar. Because of this, the texton representing a current pixel is only an approximation of the appearance of the original exemplar pixel. This approximation introduces errors into the synthesis process and degrades synthesis quality.
A second drawback to the texton-based texture synthesis is that distances in the appearance space obtained after exemplar transformation are expensive to compute because the space has many dimensions. This leads to inefficient processing. Texton-based texture synthesis techniques typically require the pre-computation and storage of a large inter-texton distance matrix. The inter-texton distance matrix is used to perform an explicit look-up in order to determine the distance between textons. Storing the inter-texton distance matrix may use a great deal of memory, since the inter-texton distance matrix can be quite large. Moreover, making random accesses to memory to perform look-ups also is memory inefficient.